
        <html>
			<head>
			     <title>通过灰盒Fuzzing技术来发现Mac OS X安全漏洞 - vvun91e0n</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/tips/6972">http://drops.wooyun.org/tips/6972</a></h1>
				
      <p>
        <p>通过灰盒Fuzzing技术来发现Mac OS X安全漏洞</p>

<p>翻译-原文地址：security.di.unimi.it/~joystick/pubs/eurosec14.pdf</p>

<p>注：部分不太重要的没有翻译。</p>

<h1>0x01 前言</h1>

<hr />

<p>内核是所有操作系统的核心，它的安全性非常重要。任何地方一个漏洞，都足以危害整个系统的安全。非特权用户如果找到这样的漏洞可以轻松的使整个系统崩溃，也或者取得管理员权限。可见，内核对攻击者来说更具吸引力，内核漏洞的数量也在以一个不安的趋势在上升。因为太复杂。在内核层挖掘漏洞是一件让人畏惧的事情。的确，现代内核是非常的复杂还含有很多子系统，有些是第三方开发的。通常，第三方开发的内核扩展组件没有内核本身那样安全。因为第三方组件不是开源的，也缺乏足够的测试。另外，内核有太多的用户数据接口。系统调用，文件系统和网络连接等允许用户提交数据到重要的代码路径。如果在其中找到一个bug，足以威胁到系统安全。测试用户层到内核的接口十分重要，因为它能够实现提权攻击。这是现在大多数攻击者想做的。</p>

<!--more-->

<p>Windows和Linux系统的内核接口已经被深入的分析，并且有很多工具用来进行检测。但在Mac OS X上，内核提供给扩展的接口交互方法相对来说还没有被广泛深入的分析。另外，OS X系统的市场份额正在稳步提升，它将吸引更多的网络犯罪分子的注意力。本文中，我们阐述了一个自动在内核扩展中发现漏洞的framework。LynxFuzzer的设计和实现。其可以自动加载Mac OS X的内核组件。OS X内核扩展称作Kext。使用苹果公司提供的IOKit framework来进行开发。LynxFuzze使用灰盒fuzzing技术动态的生成测试数据。其机理是自动从内核扩展中提取数据，并使用它们来动态生成输入数据。进一步说，我们在LynxFuzzer中实现了3种不同的fuzzing引擎：简单数据引擎的是根据内核扩展定义来产生伪随机输入数据。突变引擎是根据嗅探到的合法数据来进行变异来生成输入数据。最后一个是进化引擎，根据进化算法，使用代码覆盖率来作为主要的验证特征。</p>

<p>我们决定在开源的，通过硬件辅助的虚拟化内核调试器HyperDbg的基础上开发LynxFuzzer。主要是因为Mac OS X在现有的虚拟化软件中运行会遇到很多困难。实际上苹果公司一向以其定制化硬件出名。并不能被普通的调试器模拟。这个缺点阻碍了LynxFuzzer测试一些OS X上的驱动。另外，一个硬件辅助环境可以保证在系统崩溃时，收集到关于机器的动态信息。总的来说我们的工作做出了一下几点成果：</p>

<p>我们设计了LynxFuzzer来自动发现内核扩展的漏洞，比如动态的加载内核模块。我们解决了几个实际困难来实现这一有效的fuzzing系统。</p>

<p>我们发明了一些有效的透明的技术来自动生成fuzzing输入，从而减少输入的搜寻范围，提高对Mac OS X用户态和内核交互接口fuzzing的效率。</p>

<p>我们扩展了一种fuzzing系统。并且在一些扩展上做了实践。我们的实验发现了6个bug。在我们分析的17个扩展之中。其中两个已经在OS X 10.9种被修补。其CVE编号为CVE－2013-5166和CVE－2013-5192。</p>

<h1>0x01 IOKit基础</h1>

<hr />

<p>在这一节中，我们将要简要介绍IOKit framework。这是理解LynxFuzzer的基础。</p>

<p>Mac OS X是苹果公司开发的操作系统，用于苹果电脑。在它的众多组件中，IOKit是对我们来说是特别重要的。IOKit是一个系统框架，库，工具和其他资源的集合。用来在OS X上开发设备驱动。它提供了一个面向对象的编程环境，和一些使得开发内核组件更加简单，用户体验更好的抽象对象。在下面结合我们的工作来做一些阐述。</p>

<p>任何一个OS的基本组件就是用户态与内核空间的交互通信组件。Windows和Linux通过系统调用system call和特殊的虚拟文件(例如：／dev／urandom)。IOKit支持这两种技术，但是还新增了一种新奇的更加复杂的机制，叫做设备接口(DevieceInterface)。</p>

<p><img src="http://static.wooyun.org//drops/20150714/20150714070812318118291c5130eb4cecec731269c8061d0ad" alt="enter image description here" /></p>

<p>为了实现这种机制，内核扩展定义了一系列的可以在用户态被调用的方法。这些方法返回的参数的数量和数据的类型是被限制的。这些方法的列表和参数的限制都都存贮在被极度重要的结构体里面：这就是分派表(dispatch table)。每一个kext都可以定义一个或多个分派表。每个表都是一组结构体。每一个都包含了一个函数指针，允许的输入值和输出值，还有该方法允许接收或返回的值的数量和大小。如果输入结构体的大小不需要在输入前检验，可以将大小在表中声明为0xffffffff，然后由接收函数进行检验。任何驱动都可以拥有一个以上的分派表。IOKit允许扩展在同一时刻提供给用户空间程序以多个接口。每个kext都必须为每一个接口定义一个UserClient的子类。这些子类的实例随后与kext一起加载到内核内存(图2)。每一个UserClient对象都包含一个与它提供接口对应的分派表。</p>

<p><img src="http://static.wooyun.org//drops/20150714/2015071407081390886448298393f99a92223f8905ec6f0cbb8" alt="enter image description here" /></p>

<p>用户态程序可以通过IoConnectCallMethod()来调用kext的方法，前提是这个方法已经在kext分派表中。当然，用户态程序需要必须先找到目标实例。想解释这一过程，我们首先需要介绍一个IOKit抽象类：IOService。每一个IOKit设备驱动都是继承于它的对象，一个kext可以同时拥有不同的IOService对象。举例说明，具有代表性的就是同时有几个USB设备连接到电脑，每个都需要它自己的驱动。这些驱动都被包含在IOUSBFamily kext中，每一个都是一个特殊的IOService的子类。当一个用户态程序想要和一个设备交互时，像前面提到的一样，它会与IOKit建立一个mach连接，然后寻找合适的服务来适应设备。这个过程叫做Device Matching。</p>

<p>如果找到服务成功，交互通道也成功建立，用户态程序就会使用IoConnectCallMethod()来调用目标方法。在真正执行目标函数之前，程序会将控制权交给IOKit framework，由IOKit framework执行一系列操作。首先，它查询UserClient对象的分派表入口。入口地址随后被传送给externalMethod()函数，同时还有其他被执行调用kext方法所允许的参数。只有参数符合分派表要求的情况下，方法才会被调用，不然就会被阻止。</p>

<p>相对于一般的机制，如ioctl，整个IOKit输入控制机制提供了一个保护层。参数检查会在由用户层进入驱动层之前进行。显而易见，这些约束都使得fuzzing工作变得更加复杂。使用完全随机的参数大小来对kext的函数进行fuzz几乎是无效的。绝大多数的调用请求都会被IOKit检查并丢弃掉。我们在下一节会看到，我们fuzzer的重要一个特性就是能自动从目标中提取到参数限制，之后动态适应限制，让fuzzing更加的高效。</p>

<h1>0x02 LynxFuzzer</h1>

<hr />

<p>我们fuzzer的目的是在能被用户态程序调用到的kext code中发现bugs。一个可以从用户态激发的bug可以让非特权用户崩溃掉整个系统的。也甚至是执行任意内核代码。从而达到提权攻击。所以，我们决定将我们的注意力集中到设备接口跨界机制(DeviceInterface boundary-crossing mechanism)，因为它是OS X内核扩展机制中用户层和内核交互的标准。</p>

<p>在上一节中，需要指出的是在调用一个kext方法时，很多的约束必须得到考虑。对于每个kext来说是不同的。知道分派表中的约束能减小我们fuzzing工作量。提高fuzzing的效率。所以我们设计的LynxFuzzer能够全自动的提取信息，然后自动的进行fuzz。当然，我们的fuzzing基础设计的自动化功能不止于此。事实上，我们能提取到在用户态和内核态组件非人工交互的合法有效输入向量。这些输入可以经过精心使用来加强我们的fuzzing策略。</p>

<p><img src="http://static.wooyun.org//drops/20150714/201507140708138891662aabce2c8a95115ac7c01f0516c34f5" alt="enter image description here" /></p>

<p>LynxFuzzer的基本结构可以从图3中看到，框架拥有两个主要的组件：一个在用户态，有4个子组件构成。另一个构建在调试器分析框架上。图3中还说明了LynxFuzzer内部组件的主要交互行为。tracer和调试器(hypervisor)交互得到目标分派表。一旦发现，调试器就从内核内存中取回分派表的地址，返回给tracer，tracer将其保存到data manager中以待后面使用。sniffer使用这些信息来拦截非人工的IoConnectCall()调用，收集到一些有效的输入。最后fuzzer组件开始使用自定义的参数来调用目标方法。等待最后的异常。fuzzer可以使用之前存贮的数据生成新的输入数据或者使用覆盖突变方法来生成输入，这取决于fuzzer引擎的选择。</p>

<h2>2.1 Tracer</h2>

<hr />

<p>tracer是LynxFuzzer的第一个运行的组件，它的任务是找到fuzz的目标。举例，它必须确定目标的哪个方法是能够被调用的。这些信息包含在目标kext的分派表中。然而，定位一个kext的分派表并不简单，因为IOKIt使用很多抽象层来对用户层隐藏信息。我们的解决方案是：任何时候用户态程序调用IoConnectCallMethod()，IOKit将会调用它的externalMethod()函数，我们对此进行监视。通过以下方法来实现，LynxFuzzer调试器对externalMethod()函数下一个断点，截断对它的调用。一旦这个陷阱(trap)被设置好，tracer就对目标kext发起一个请求，其selector参数为0。当调试器截断externalMethod()，就提取分派表的基地址。然后dump整个分派表，将它返回给tracer。最终，tracer存贮分派表到data maanger，分享给其它组件使用。</p>

<p>分派表的大小事先是不知道的。也不在被截断函数的参数里面。为了解决这个问题，LynxFuzzer分析分派表的结构推断出其拥有多少个入口，然后dump下来。事实上，每个表的入口由一个指针，该指针必须在目标的内存范围内。和4个连续的整数，其中两个必须在0-15之间。</p>

<h2>2.2 Sniffer</h2>

<hr />

<p>除了IOKit的检查，kext自己可以实现对输入的约束。所以LynxFuzzer包含了一个sniffer组件。该组件用来截断目标方法的执行，提取到它们的参数。为了实现这个我们再次利用LynxFuzzer的调试器，它可以透明的无缝的截断我们感兴趣的函数，通过检查目标kext的内存来dump它的参数。</p>

<p>特别的，调试器对于externalMethod()函数来说是透明的。该函数的参数包含了足够的信息来获取有效的输入。事实上，调试器用dispatch参数来区分出是哪一个kext是这次截断的目标。用selector参数来确定是哪一个方法被调用。IOExternalMethodArguments结构中包含了真正的传递进来的参数。这种结构中还包含了参数的数量和大小。它们都将会被保存到data manager。</p>

<h2>2.3 Fuzzer</h2>

<hr />

<p><img src="http://static.wooyun.org//drops/20150714/2015071407081354802b8c28711958cf7257da72b3081de8242" alt="enter image description here" /></p>

<p>fuzzer是LynxFuzzer的主要组件。当tracer盒sniffer获取了足够的辅助信息可以进行fuzz一个kext时，fuzzer生成对kext方法的测试集，然后通过IOKit设备接口来调用方法。图4显示了该组件的结构：一个请求生成器，一组fuzzing引擎和一个监视器。 请求生成器是一个通用的组件：它必须独立于目标kext和选择的fuzzing引擎来运转。在一次典型的执行中，它从fuzzing引擎中接收到测试数据之后，检查数据是否符合分派表中声明目标方法的要求，适当的调整以符合最后在kext中执行目标方法的IoConncetCallMethod()函数. 如果测试数据没有导致崩溃，kext发出一个回应，由monitor来接收。monitor根据接收到的放回数据和当前的fuzzing引擎来决定是否继续使用当前的引擎。所以后一个测试基于前一个测试反馈的。突变引擎和进化引擎都会使用该模式。</p>

<p>LynxFuzzer实现了基于会话的fuzzing：我们不多余操作，只需要发出寻找bug的请求。但是我们要从每个fuzzing会话开始记录每一个请求。这种方法很常见，特别是在fuzzing基于状态的网络协议的时候，在这种情景下也是适用的。事实上kext也拥有一种状态。这种状态会随着大量不同的fuzzing请求而变化，直到进入非正常的状态，一个bug被触发。出于这种原因，使用基于会话的记录，代替单个的请求会极大的保证一个bug的可重现性。记录fuzzer和目标kext之间的交互会话，每一个请求都被存贮在data manager中，最终fuzzer对输入数据的生成也是由影响的。LynxFuzzer三种不同引擎的细节我们马上给出。</p>

<h3>2.3.1 随机引擎（Generation Engine）</h3>

<p>这是最简单快速的引擎。它的生成过程可以简述如下，第一步，它生成可以包含输入数据到目标方法的数据结构。第二步，生成伪随机数据来填充这个结构体。最后，将数据通过IoConnectCallMethod()发送给目标。如果系统没有崩溃就继续反复这一过程。</p>

<h3>2.3.2 突变引擎（Mutation Engine）</h3>

<p>这种fuzzing方法遵循一个原则就是站在前者数据的对立面：每一个新的输入数据都是从sniffer组件收集到的有效输入数据变化生成。fuzzing的过程也比较简单：使用不同的突变函数将sniffer收集到的有效输入数据进行变异，然后使用突变后的数据进行请求。如果系统没有崩溃，monitor会检查kext给出的返回值。尽可能的将会导致kext返回error的输入值排除在下一个突变生成之外。这极大的提高了fuzzer的效率。特别是在输入结构时可变大小的时候，因为它逐步去除了那些在目标方法中被检查非法的输入。这个引擎使用的突变函数有：位翻转，字节翻转，字节交换和大小改变。</p>

<h3>2.3.3 进化引擎（Evolution Engine）</h3>

<p>进化引擎试图突破其他引擎的限制。尽量少的使用伪随机。利用进化算法来生成新的输入数据。</p>

<p>任何进化算法的核心就是适应函数(fitness function)。它定义了生成器使用的最佳元素。在LynxFuzzer里，我们开发了两种适应函数：一个测量输入向量的代码的覆盖率。另一个测量输入和最佳输入向量(导致崩溃的输入)的差距。在第一种情况中，我们极力去生成一组输入向量来给我们最佳的代码覆盖率。第二种情况在我们想在定制一个给定向量(比如一个会触发bug的向量)的时很有用。</p>

<p>代码覆盖率分析。我们的代码覆盖率分析方法如下：在开始调用kext方法之前，fuzzer组件告知调试器kext的代码范围。调试器将相应代码内存段的可执行属性在EPT(Extended Page Tables)入口中移除。这样只要kext执行相应页的代码时就会触发一个EPT违规。调试器跟踪到导致违规的指令。为了继续，调试器重新将不可执行夜标志为可执行，同时让程序单步执行。当调试器由于调试异常而重新获得控制权，它再将这个可执行权限移除，所以下一个指令还是会产生执行违规。当被fuzz的方法返回，fuzzer发出调用来解除跟踪。调试器存贮收集到的信息到fuzzer的一块空间中，让用户空间的组件来计算相应调用的代码覆盖率。</p>

<p><img src="http://static.wooyun.org//drops/20150714/2015071407081358813a508dbd446ead58505abf2705d17900e" alt="enter image description here" /></p>

<h1>0x03 实验评估</h1>

<hr />

<p>本节介绍下我们测试LynxFuzzer效率的的实验。我们测试了17个同的内核扩展。找到了6个bug。其中2个已经在OS X 10.9中得到了修复。已经被苹果公司定义为CVE-2013-5166和CVE-2013-5192。剩下的4个还没有被修复。也许会在以后版本中修复。</p>

<p>所有的的实验都是在安装来Mac OS X 10.8.2系统的苹果电脑(Intel i5 CPU 12G RAM)上进行的。由于苹果内核的安全机制。我们找到的漏洞没有一个可以简单溢出进行提权的攻击的。</p>

<p>评价fuzzer效率的的其中一个指标就是代码覆盖率水平。这个指标也许不是那么的绝对：一个fuzzer也许代码覆盖率达到100%也获取不了一个bug。但是通常都会报告这一指标，所以我们统计了LynxFuzzer的代码覆盖率。</p>

<p>虽然我们的调试器可以轻松的追踪每一条指令。但是给出一个精确的覆盖率还是相当不容易的。我们通过静态动态混合分析技术来估算出可以有分派表达到的代码总量。首先，我们静态的计算导出方法的指令数。塞选出所有控制转移指令CTI(control transfer instrction)。然后，对于每个CTI，如果跳转目标是同一个kext的另一个方法，我们就将其统计到总数中。</p>

<p>不幸的是这还是有不足之处。由于内核的面相对象特性，kext包含很多间接CTI，无法静态跟踪。对于这类指令，我们采用动态分析：我们改进了LynxFuzzer代码覆盖率分析模型，让它dump每一条kext中每一条CTI指令的目标。如果目标在静态分析中没有被检测到，我们还是将这个指令计算到总数中。</p>

<p>表1显示了一部分代码覆盖率的实验结果。在覆盖率栏我们显示了3种不同的覆盖率百分比：导出方法的指令数，混合分析的指令数，kext中指令总数。</p>

<p>我们还估算了在3.3中描述的代码覆盖率方法的开销。为此，我们在10个不同kext上运行随机引擎fuzz每个方法。将代码覆盖率统计模块分别开启和关闭，统计kext每秒可以处理的请求数。出于精确性，我们在每个模块上进行了10次重复。结果取平均值。平均开销是3.45x，最优和最差分别是1.73x和5.99x。表2给出了细节。我们可以看到，我们为获取高精度，在没有优化目标时付出了较大的代价，但是相对其他技术来说也算是很低了。</p>

<p><img src="http://static.wooyun.org//drops/20150714/201507140708146122232b19dd5f39f0140d67f3821e49794c5" alt="enter image description here" /></p>

<p>最后，评估了引擎的效率，特别指出，通过不同配置的我们的引擎都能用于发现bug，但是基于代码覆盖率的进化引擎是最快的，随机引擎最慢。</p>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          